import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

//leetcode 51 N皇后

/**
 * 思路就是通过决策树的方式来列举出可能的情况，但是由于一个格子一个格子列举的话时间复杂度很高，所以就可以一次决定
 * 一行中皇后存在的位置，因为一行也只能存在一个皇后，不同的就是皇后的位置可以变化
 */
public class Test2 {
    char[][] path;
    //checkDig1是用来记录正对角线上的点是否有皇后，最大的正对角线上y=x，其他的对角线就可以用y=x+n来表示，所以一个对角线上的点x-y+n的值是相同的，就可以用check[x-y+n]来记录正对角线上是否有皇后
    //checkDig2使用来记录副对角线上是否有皇后的，原理和checkDig1类似
    boolean[] checkCol, checkDig1, checkDig2;
    List<List<String>> ret;
    int n;
    public List<List<String>> solveNQueens(int _n) {
        n = _n;
        path = new char[n][n];
        checkCol = new boolean[n];
        checkDig1 = new boolean[2 * n];
        checkDig2 = new boolean[2 * n];
        ret = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            Arrays.fill(path[i], '.');
        }
        dfs(0);
        return ret;
    }

    private void dfs(int cow) {
        if (cow == n) {
            List<String> tmp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                tmp.add(new String(path[i]));
            }
            ret.add(new ArrayList<>(tmp));
        }
        //这个循环就是为了例举出每一行中所有列的位置
        for (int i = 0; i < n; i++) {
            if (!checkCol[i] && !checkDig1[cow - i + n] && !checkDig2[cow + i]) {
                path[cow][i] = 'Q';
                checkCol[i] = checkDig1[cow - i + n] = checkDig2[cow + i] = true;
                dfs(cow + 1);
                path[cow][i] = '.';
                checkCol[i] = checkDig1[cow - i + n] = checkDig2[cow + i] = false;
            }
        }
    }
}
